引子

现在, 你有一个递推式, 或者称之为递归关系, 如下:
$$f(n) = f(n - 1) + f(n - 2)$$
$$f(1) = f(2) = 1, n >= 1$$
聪明人一看, 啊这不是斐波那契数列吗, 这我会!!!
于是, 我们的聪明人同学很快啊, 很快写出了这样的代码:

循环法

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n, fab[10001];
    fab[1] = 1, fab[2] = 1;
    for(int i = 3; i <= 10000; ++ i){
        fab[i] = fab[i - 1] + fab[i - 2];
    }
    scanf("%d", &n);
    printf("%d\n", fab[n]);
    return 0;
} // 此代码计算到 f(79) 就出现了越界的情况

using System;
namespace Faboric
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] fab = new long[10001];
            fab[1] = 1;
            fab[2] = 1;
            for (int i = 3; i < 10001; ++ i)
            {
                fab[i] = fab[i - 1] + fab[i - 2];
            }
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine(fab[n]);
            Console.ReadLine();
        }
    }
} // 此代码计算到 f(197) 出现越界

fab = []
fab.append(1)
fab.append(1)
n = int(input("n:"))
for i in range(3, n + 1, 1):
    fab.append(fab[len(fab) - 1] + fab[len(fab) - 2])
print(fab[n - 1])
# 此代码理论上可以无限计算, 本人 python 学的不好, 计算到 f(500000) 时出现明显卡顿

这三个代码都使用了循环来计算斐波那契数列, 聪明人同学看了一眼书本目录, 又立马大喊道:”老师, 我还可以用递归写!!!”
于是, 他马上又写出了这样的代码:

递归法

#include <bits/stdc++.h>
using namespace std;
long long f(int n){
    if(n == 1 || n == 2) return 1;
    else return f(n - 1) + f(n - 2);
}
int main(){
    int n;
    scanf("%d", &n);
    printf("%lld\n", f(n));
    return 0;
}

此代码计算到 f(48) 时等待了约莫 16 秒, 因为这个递归会完全忽略上一轮已经计算过的, 造成时间复杂度高昂
配合记忆化的思想, 这个代码可以这么写:

#include <bits/stdc++.h>
using namespace std;
long long via[100001];
long long f(int n){
    if(n == 1 || n == 2) return 1;
    else{
        long long tmp = (via[n - 1] == 0 ? f(n - 1) : via[n - 1]) + (via[n - 2] == 0 ? f(n - 2) : via[n - 2]);
        via[n] = tmp;
        return tmp;
    }
}
int main(){
    via[1] = via[2] = 1;
    int n;
    scanf("%d", &n);
    printf("%lld\n", f(n));
    return 0;
}

此时 f(48) 已经降到了 0.2 秒左右, 已经很快了, 同时运行到 f(93) 才出现越界的情况:

92
7540113804746346429

--------------------------------
Process exited after 0.6031 seconds with return value 0
请按任意键继续. . .

using System;
namespace Faboric
{
    class Program
    {
        static long[] via = new long[100001];
    
        static long f(int n)
        {
            if(n == 1 || n == 2) return 1;
            else
            {
                long tmp = (via[n - 1] == 0 ? f(n - 1) : via[n - 1]) + (via[n - 2] == 0 ? f(n - 2) : via[n - 2]);
                via[n] = tmp;
                return tmp;
            }
        }
        
        static void Main(string[] args)
        {
            for (int i = 0; i < 100001; ++i) via[i] = 0;
            via[1] = 1;
            via[2] = 1;
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine(f(n));
            Console.ReadLine();
        }
    }
} // 依旧是计算到 f(197) 出现越界

via = []

def f(n):
    if(n == 1 or n == 2): return 1
    else:
        tmp = (f(n - 1) if via[n - 1] == 0 else via[n - 1]) + (f(n - 2) if via[n - 2] == 0 else via[n - 2])
        via[n] = tmp
        return tmp
    
if __name__ == "__main__":
    n = int(input("n:"))
    for i in range(0, n + 1, 1):
        via.append(0)
    print(f(n))
# 同样地使用记忆化的思想, python 的递归也可以达到较高的速度

终于, 老师开口了:”骚年, 你的计算机程序设计基础学的还是可以的, 但是你的数学, 可就没那么好了”
于是, 老师开始了今天的课程

特征方程

特征方程详解

对于任意一个递归关系如果满足:
$$F(n) = {a_1}F(n-1) + {a_2}F(n-2) + \cdots + {a_k}F(n-k),\quad a_k \neq 0$$
则称此递归关系为 k 阶的线性常系数齐次递归关系

如果你的递归关系符合📎线性常系数齐次递归关系, 那么你的递归关系就可以简单地求出一个通项公式, 也就是你的递推式的通解
所谓的线性常系数齐次递归关系就是指:

线性 : 所有的 f 都是一次的
常系数 : $c _ 1$, $c _ 2$, $\ldots$ $c _ n$ 这些系数都是常数
齐次 : 所有的 f 的次数都是相同的
而特征方程的一般形式是:
$$f(n) = c _ 1 x _ 1 ^ n + c _ 2 x _ 2 ^ n + \cdots + c _ n x _ n ^ n$$
所有的这些 $x _ 1$ , $x _ 2$, $\ldots$ $x _ n$ 这些就叫做特征根
我们只需要通过原递归关系解出这些特征根, 再通过一些已知值解出 $c _ 1$, $c _ 2$ 这些东西, 那么原递归关系的通解就出来了

使用特征方程解出斐波那契数列的通项公式

以斐波那契为例:
$$f(n) = f(n - 1) + f(n - 2)\quad n \in N$$
$$\Rightarrow x ^ n \quad = \quad x ^ {n - 1} \quad + \quad x ^ {n - 2}$$
移项, 提取公因式得:
$$x ^ {n - 2} (x ^ 2 - x - 1) = 0$$
由斐波那契的性质可知:
$$f(n) \neq 0$$
$$\therefore x ^ {n - 2} \neq 0$$
$$\therefore x ^ 2 - x - 1 = 0$$
解得:
$$x _ 1 = \frac{1 + \sqrt{5}}{2}, x _ 2 = \frac{1 - \sqrt{5}}{2}$$
带入特征方程, 得:
$$f(n) = c _ 1 {(\frac{1 + \sqrt{5}}{2})} ^ n + c _ 2 {(\frac{1 - \sqrt{5}}{2})} ^ n$$
再带入 f(0) = f(1) = 1,

这里有的同学可能就要问了, 不是 f(1) = f(2) = 1 嘛
其实是这样的, 当 n 为 0 时可以得到一个方程为 $c_1 + c_2 = 1$ 方便计算
等计算完之后再把等式右边的所有 n 都减一就恢复成了 f(1) = f(2) = 1 了

得到方程组:
$$
\begin{cases}
c_1 + c_2 = 1 \\
c_1(\frac{1+\sqrt{5}}{2}) + c_2(\frac{1-\sqrt{5}}{2}) = 1 \\
\end{cases}
$$
解得:
$$
\begin{cases}
c_1 = \frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2}) \\
c_2 = - \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2}) \\
\end{cases}
$$
带回到特征方程, 得到完整的通解表达式:
$$f(n) = \frac{1}{\sqrt{5}}{(\frac{1+\sqrt{5}}{2})}^{n+1} - \frac{1}{\sqrt{5}}{(\frac{1-\sqrt{5}}{2})}^{n+1}$$
对其进行复原到 f(1) = f(2) = 1 的操作, 得:
$$f(n) = \frac{1}{\sqrt{5}}{(\frac{1+\sqrt{5}}{2})}^n - \frac{1}{\sqrt{5}}{(\frac{1-\sqrt{5}}{2})}^n$$
简单验算可以看到这个公式是正确的
将其转化为等效的代码时只需注意一下精度的问题, 别整溢出了

实战演练

打开📎信息学奥赛一本通官网, 关于 Pell 数列这题就是应用特征根的绝佳之处
虽然我用这个法子没过😭
关于这题的大致情况是, 对于每个输入的 k , 要求 f(k) 的值 mod 32767 的值
对于 f(k) 定义如下:
$$f(k) = 2f(k-1) + f(k-2),\quad k>2 \quad 且 \quad k \in N$$
且已知: $f(1)=1,\quad f(2)=2$
咋一看, 与斐波那契数列如同一个模子刻出来的, 再仔细一看, 完全符合线性常系数齐次递归关系的定义, 于是, 我们有了以下求解过程:
$$
\begin{aligned}
f(n) = 2f(n-1) + f(n-2) \\
\\
\Rightarrow x^n = 2x^{n-1} + x^{n-2} \\
\\
\therefore x^n - 2x^{n-1} - x^{n-2} = 0 \\
\\
x^{n-2}(x^2 - 2x - 1) = 0 \\
\\
\because x^{n-2} \neq 0 \\
\\
\therefore x^2 - 2x - 1 = 0 \\
\end{aligned}
$$
$$
\Rightarrow
\begin{cases}
x_1 = 1 + \sqrt{2}, \\
\\
x_2 = 1 - \sqrt{2} \\
\end{cases}
$$
$$\therefore f(n) = c_1(1+\sqrt{2})^n + c_2(1-\sqrt{2})^n$$
令 $f(0) = 1,\quad f(1) = 2$
则:
$$
\begin{cases}
c_1 + c_2 = 1, \\
\\
c_1(1 + \sqrt{2}) + c_2(1 - \sqrt{2}) = 2 \\
\end{cases}
$$
解得:
$$
\begin{cases}
c_1 = \frac{2+\sqrt{2}}{4} \\
\\
c_2 = \frac{2-\sqrt{2}}{4} \\
\end{cases}
$$
再考虑复原 $f(0) = 1,\quad f(1) = 2$ 到 $f(1)=1,\quad f(2)=2$ 的操作:
最终, 通解为:
$$f(n) = \frac{2+\sqrt{2}}{4}(1+\sqrt{2})^{n-1} + \frac{2-\sqrt{2}}{4}(1-\sqrt{2})^{n-1}$$